/**
 * Created by L.jp
 * Description:有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
 *
 * 问最多能装入背包的总价值是多大?
 * User: 86189
 * Date: 2021-11-12
 * Time: 23:11
 */
public class KnapsackProblemTwo {
        /**
         * @param m: An integer m denotes the size of a backpack
         * @param A: Given n items with size A[i]
         * @param V: Given n items with value V[i]
         * @return: The maximum value
         */
        public int backPackII(int m, int[] A, int[] V) {
            //方法一：建立二维数组，i表示物品数，j表示当前背包的容量
            /*
            int n=A.length;//物品个数
            int[][] maxValue=new int[n+1][m+1];//存储最大价值
            //当i=0,j=0是，默认最大价值都是0，作为初始值
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    if(A[i-1]<=j){//如果背包里面还有空间可以放,i-1表示的就是数组里第i个物品的意思，数组里面i是从0开始的
                        maxValue[i][j]=Math.max(maxValue[i-1][j],maxValue[i-1][j-A[i-1]]+V[i-1]);//此时当前背包的最大价值就是取不放和放的两者的最大价值
                                                                                                // 如果是不放的话，那么就是当前背包容量下上一个物品的最大价值
                                                                                                //如果放的话，那么就要先把当前背包剩下的空间先算出最大价值，然后再加上这个物品的价值
                    }else{
                        maxValue[i][j]=maxValue[i-1][j];//如果背包不能放，那么就最大价值就是i-1个物品的最大价值
                    }
                }
            }
            return maxValue[n][m];//返回最后一行最后一列元素所代表的最大价值

             */
            //方法二，创建一维数组来保存当前背包所拥有物品的最大值，maxValue[j]表示当前背包的最大价值，不用表示物品数
            int n=A.length;//物品个数
            int[] maxValue=new int[m+1];//存储最大价值
            //当i=0,j=0是，默认最大价值都是0，作为初始值
            for(int i=1;i<=n;i++){
                for(int j=m;j>=0;j--){
                    if(A[i-1]<=j) {//如果背包里面还有空间可以放，i-1表示的就是数组里第i个物品的意思，数组里面i是从0开始的
                        maxValue[j] = Math.max(maxValue[j], maxValue[j - A[i - 1]] + V[i - 1]);//此时当前背包的最大价值就是取不放和放的两者的最大价值
                        // 如果是不放的话，那么就是当前背包容量的最大价值
                        //如果放的话，那么就要先把当前背包给第i个物品腾出的空间的最大价值，然后再加上这个物品的价值
                    }
                    //如果A[i-1]>j的话，那么当前背包最大值就是maxValue[j],不用写出来；
                }
            }
            return maxValue[m];//返回最后一行最后一列元素所代表的最大价值
        }
}
